package com.jiang.daily.Q3373;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/05/29 16:25
 */
// class Solution {
//     public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
//         int n = edges1.length + 1;
//         int[] cnt1 = buildCnt(edges1, 0);
//         int[] cnt2 = buildCnt(edges2, 1);

//         int maxCnt2 = 0;
//         for (int c : cnt2) {
//             maxCnt2 = Math.max(maxCnt2, c);
//         }

//         int[] res = new int[n];
//         for (int i = 0; i < n; i++) {
//             res[i] = cnt1[i] + maxCnt2;
//         }
//         return res;
//     }

//     private int[] buildCnt(int[][] edges, int cnt) {
//         int len = edges.length + 1;
//         List<List<Integer>> list = new ArrayList<>();
//         for (int i = 0; i < len; i++) {
//             list.add(new ArrayList<>());
//         }

//         for (int[] edge : edges) {
//             list.get(edge[0]).add(edge[1]);
//             list.get(edge[1]).add(edge[0]);
//         }

//         int[] res = new int[len];
//         for (int i = 0; i < len; i++) {
//             dfs(i, -1, i, list, cnt, res);
//         }

//         return res;
//     }

//     private void dfs(int cur, int pre, int start, List<List<Integer>> list, int cnt, int[] res) {
//         if (cnt % 2 == 0) {
//             res[start]++;
//         }

//         for (int next : list.get(cur)) {
//             if (next == pre) {
//                 continue;
//             }
//             dfs(next, cur, start, list, cnt + 1, res);
//         }
//     }
// }

class Solution {
    public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
        int n = edges1.length + 1, m = edges2.length + 1;
        int[] color1 = new int[n];
        int[] color2 = new int[m];
        int[] count1 = build(edges1, color1);
        int[] count2 = build(edges2, color2);
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = count1[color1[i]] + Math.max(count2[0], count2[1]);
        }
        return res;
    }

    private int[] build(int[][] edges, int[] color) {
        int n = edges.length + 1;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            children.get(edge[0]).add(edge[1]);
            children.get(edge[1]).add(edge[0]);
        }
        int res = dfs(0, -1, 0, children, color);
        return new int[]{res, n - res};
    }

    private int dfs(int node, int parent, int depth, List<List<Integer>> children, int[] color) {
        int res = 1 - depth % 2;
        color[node] = depth % 2;
        for (int child : children.get(node)) {
            if (child == parent) {
                continue;
            }
            res += dfs(child, node, depth + 1, children, color);
        }
        return res;
    }
}

